#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <unordered_map>
#include <string>
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            int tmp = target - nums[i];
//            if (hash.count(tmp))
//                return { hash[tmp],i };
//            hash[nums[i]] = i;
//        }
//        return {};
//    }
//};
//class Solution {
//public:
//    bool CheckPermutation(string s1, string s2) {
//        if (s1.size() != s2.size())
//            return false;
//        unordered_map<char, int> hash;
//        for (auto e : s1)
//        {
//            hash[e]++;
//        }
//        for (auto e : s2)
//        {
//            if (hash[e] == 0)
//                return false;
//            hash[e]--;
//        }
//        return true;
//    }
//};
//class Solution {
//public:
//    bool containsDuplicate(vector<int>& nums) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            hash[nums[i]]++;
//            if (hash[nums[i]] >= 2)
//                return true;
//
//        }
//        return false;
//    }
//};

//class Solution {
//public:
//    bool containsNearbyDuplicate(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (hash.count(nums[i]))
//            {
//                if (i - hash[nums[i]] <= k)
//                    return true;
//
//            }
//            hash[nums[i]] = i;
//        }
//        return false;
//    }
//};

//class Solution {
//public:
//    vector<vector<string>> groupAnagrams(vector<string>& strs) {
//        vector<vector<string>> ret;
//        unordered_map<string, vector<string>> hash;
//        for (auto e : strs)
//        {
//            string tmp = e;
//            sort(tmp.begin(), tmp.end());
//            hash[tmp].push_back(e);
//        }
//        for (auto e : hash)
//        {
//            ret.push_back(e.second);
//        }
//        return ret;
//    }
//};
//
//bool isInTree(TreeNode* root, TreeNode* target)
//{
//    if (root == nullptr)
//        return false;
//    if (root == target)
//        return true;
//    return isInTree(root->left, target) || isInTree(root->right, target);
//}
//class Solution {
//public:
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (p == root || q == root)
//            return root;
//        bool pLeft = isInTree(root->left, p);
//        bool pRight = isInTree(root->right, p);
//        bool qLeft = isInTree(root->left, q);
//        bool qRight = isInTree(root->right, q);
//
//        //else if(q==root&&(pLeft||pRight))
//            //return root;
//        if ((qLeft && pRight) || (qRight && pLeft))
//            return root;
//        else if (qLeft && pLeft)
//            return lowestCommonAncestor(root->left, p, q);
//        else if (qRight && pRight)
//            return lowestCommonAncestor(root->right, p, q);
//        return nullptr;
//    }
//};
//
//class Solution {
//public:
//
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        vector<TreeNode*> path1;
//        vector<TreeNode*> path2;
//        dfs(root, p, path1);
//        dfs(root, q, path2);
//        unordered_map<TreeNode*, int> hash;
//        for (auto e : path1)
//        {
//            hash[e]++;
//        }
//        TreeNode* ret = nullptr;
//        for (auto e : path2)
//        {
//            if (hash.count(e))
//                ret = e;
//        }
//        return ret;
//    }
//    bool dfs(TreeNode* root, TreeNode* target, vector<TreeNode*>& path)
//    {
//        if (root == nullptr)
//            return false;
//        path.push_back(root);
//        if (root == target)
//            return true;
//        bool left = dfs(root->left, target, path);
//        bool right = dfs(root->right, target, path);
//        if (left == false && right == false)
//        {
//            path.pop_back();
//            return false;
//        }
//        return true;
//    }
//};
//class Solution {
//public:
//    TreeNode* Convert(TreeNode* pRootOfTree) {
//        TreeNode* head = new TreeNode(0);
//        TreeNode* tail = head;
//        dfs(pRootOfTree, tail);
//        TreeNode* ret = head->right;
//        delete head;
//        if (ret)
//            ret->left = nullptr;
//        return ret;
//    }
//    void dfs(TreeNode* root, TreeNode*& tail)
//    {
//        if (root == nullptr)
//            return;
//        dfs(root->left, tail);
//        TreeNode* newnode = new TreeNode(root->val);
//        tail->right = newnode;
//        newnode->left = tail;
//        tail = tail->right;
//        dfs(root->right, tail);
//    }
//};
#include <vector>
struct TreeNode
{
    TreeNode(int _val)
        :val(_val)
    {}
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};
//class Solution {
//public:
//    TreeNode* buid(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
//    {
//        if (prei >= preorder.size())
//            return nullptr;
//        TreeNode* root = new TreeNode(preorder[prei]);
//        int rooti = 0;
//        for (int i = 0; i < inorder.size(); i++)
//        {
//            if (inorder[i] == preorder[prei])
//            {
//                rooti = i;
//                break;
//            }
//        }
//
//        root->left = inbegin > rooti - 1 ? nullptr : buid(preorder, inorder, ++prei, inbegin, rooti - 1);
//        root->right = rooti + 1 > inend ? nullptr : buid(preorder, inorder, ++prei, rooti + 1, inend);
//        return root;
//
//    }
//    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//        if (preorder.size() == 0)
//            return nullptr;
//        int prei = 0;
//        return buid(preorder, inorder, prei, 0, preorder.size() - 1);
//    }
//};
//
//class Solution {
//public:
//    TreeNode* buid(vector<int>& postorder, vector<int>& inorder, int& posti, int inbegin, int inend)
//    {
//        if (inbegin > inend)
//            return nullptr;
//        TreeNode* root = new TreeNode(postorder[posti]);
//        int rooti = 0;
//        for (int i = inbegin; i <= inend; i++)
//        {
//            if (inorder[i] == postorder[posti])
//            {
//                rooti = i;
//                break;
//            }
//        }
//        root->right = rooti + 1 > inend ? nullptr : buid(postorder, inorder, --posti, rooti + 1, inend);
//
//        root->left = inbegin > rooti - 1 ? nullptr : buid(postorder, inorder, --posti, inbegin, rooti - 1);
//        return root;
//
//    }
//    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//        if (postorder.size() == 0)
//            return nullptr;
//        int posti = postorder.size() - 1;
//        return buid(postorder, inorder, posti, 0, postorder.size() - 1);
//    }
//};
#include <stack>
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        if (root)
            st.push(root);
        else
            return ret;
        while (!st.empty())
        {
            TreeNode* tmp = st.top();
            if (tmp->left)
            {
                st.push(tmp->left);
            }
            else
            {

                ret.push_back(tmp->val);
                st.pop();
                if (tmp->right)
                {
                    st.push(tmp->right);
                }
                else
                {
                    TreeNode* prev = st.top();
                    while ((!st.empty()) && prev->left == tmp)
                    {
                        ret.push_back(prev->val);
                        st.pop();
                        tmp = prev;
                        if(!st.empty())
                            prev = st.top();
                    }
                }

            }

        }
        return ret;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            if (top->right == nullptr || prev == top->right)
            {
                prev = top;
                ret.push_back(top->val);
                st.pop();
                //cur = st.top();
            }
            else
            {
                cur = top->right;
                //prev = top;
            }

        }
        return ret;
    }
};

int main()
{
    //cout << Solution().CheckPermutation("abb", "aab") << endl;
    //vector<int> n1 = { 3,9,20,15,7 };
    //vector<int> n2 = { 9,3,15,20,7 };
    TreeNode* n1 = new TreeNode(1);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    n1->right = n2;
    n2->left = n3;
    Solution().preorderTraversal(n1);
    //Solution().buildTree(n1,n2);
    return 0;
}